/*
 * AbstractProbabilityVector.java
 *
 * Created on 21 de Julho de 2011, 12:24
 *
 */

package intopo.partnerselection;

import cern.jet.random.engine.MersenneTwister;

import util.math.Rational;

import java.io.Serializable;

/**
 * <p> The probability vector contains partial sums. Therefore,
 * selecting a partner has time complexity {@code log(n)}, however
 * updating the vector has time complexity {@code O(n)}, where {@code n}
 * is the number of combinations.  As games are played and if there are
 * cooperative combinations, there are fewer probability vector updates.
 *
 * @author <a href="mailto:mariano.pedro@gmail.com">Pedro Mariano</a>
 *
 * @version 1.0 21 de Julho de 2011
 */
abstract public class AbstractProbabilityVector<S extends AbstractProbabilityVector.Slot>
	implements Serializable
{
	final private S[] vector;
	/**
	 * Integer that represents the probability of a sucessfull event.  The value stored in this field is also in {@code vector[vector.length-1].probabilityPartialSum}.
	 */
	final protected transient int maxProbability;
	/**
	 * Lenght of vector minus 1.
	 */
	final protected transient int length1;
	/**
	 * Creates a new instance of AbstractProbabilityVector
	 */
	public AbstractProbabilityVector (S[] vector)
	{
		this.vector = vector;
		this.length1 = vector.length - 1;
		this.maxProbability = vector [this.length1].probabilityPartialSum;
		assert checkVector () : "Probability vector check Failed";
	}
	/**
	 * Construct an abstract probablity vector using the given parameters to initialise the probabilities in each slot.  Each slot has the same probability of being selected: {@code maxProbability/vector.length}.  Since integers are used one slot has a higher probability if the remainder of the above division is non-zero.  This slot is randomly selected.
	 * @param vector The vector that contains the probabilities and any data needed by the user of this class.
	 * @param maxProbability The integer that represents the probability of a sucessfull event.
	 * @param supply  The pseudo-random number generator used to initialise the probabilities.
	 */
	public AbstractProbabilityVector (S[] vector, int maxProbability, MersenneTwister supply)
	{
		assert this.checkVectorNullElements () : "There are null elements in the probability vector";
		this.vector = vector;
		this.length1 = vector.length - 1;
		this.maxProbability = maxProbability;
		
		int partialSum = 0;
		int initialProbability = maxProbability / vector.length;
		int remainder =  maxProbability % vector.length;
		int remainderIdx = Math.abs (supply.nextInt ()) % vector.length;
		int i = 0;
		for (; i < remainderIdx; i++) {
			partialSum += initialProbability;
			this.vector [i].probabilityPartialSum = partialSum;
		}
		partialSum += remainder;
		for (; i < vector.length; i++) {
			partialSum += initialProbability;
			this.vector [i].probabilityPartialSum = partialSum;
		}
		assert this.checkProbabilityPartialSums () : "Initialisation algorithm has bugs";
	}
	/**
	 * Return the size of the probability vector.
	 * @return the size of the probability vector.
	 */
	final public int size ()
	{
		return this.vector.length;
	}
	final public S getSlot (int index)
	{
		return vector [index];
	}
	/**
	 * Get the probability at the given slot as a rational number.
	 */
	final public Rational getProbabilityAsRational (int index)
	{
		return new Rational (this.getRawProbability (index), this.maxProbability);
	}
	/**
	 * Get the probability at the given slot as a floating point number in {@code float} precision.
	 */
	final public float getProbabilityAsFloat (int index)
	{
		return this.getRawProbability (index) / (float) this.maxProbability;
	}
	/**
	 * Get the probability at the given slot as a floating point number in {@code double} precision.
	 */
	final public double getProbabilityAsDouble (int index)
	{
		return this.getRawProbability (index) / (double) this.maxProbability;
	}
	/**
	 * Get the raw probability at the given slot in the probability vector.
	 *
	 * <p> The probability vector contains partial sums. Therefore,
	 * selecting a partner has time complexity {@code log(n)}, however
	 * updating the vector has time complexity {@code O(n)}, where {@code n}
	 * is the number of combinations.  As games are played and if there are
	 * cooperative combinations, there are fewer probability vector updates.
	 */
	final public int getRawProbability (int index)
	{
		if (index == 0) {
			return vector [0].probabilityPartialSum;
		}
		else {
			return vector [index].probabilityPartialSum - vector [index - 1].probabilityPartialSum;
		}
	}
	/**
	 * Get the maximum raw probability.
	 *
	 * <p> Probabilities are represented internally by integers from the range {@code 0} to {@code maxProbability}.  The last slot of the probability 
	 */
	final public int getMaxRawProbability ()
	{
		return this.maxProbability;
	}
	/**
	 * Return the index of a slot randomly selected using the
	 * probability vector.
	 */
	final public int randomCombination (MersenneTwister supply)
	{
		int rnd = Math.abs (supply.nextInt ()) % this.maxProbability;
		int lower = 0, upper = this.length1;
		while (upper > lower) {
			int middle = (upper + lower) / 2;
			if (this.vector [middle].probabilityPartialSum <= rnd) {
				lower = middle + 1;
			}
			else {
				upper = middle;
			}
		}
		return lower;
//		return Math.max (0, Math.min (lower, this.length1));
//		int rnd = Math.abs (supply.nextInt ()) % (this.maxProbability + 1);
//		int lower = 0, upper = this.length1;
//		while (upper >= lower) {
//			int middle = lower + (upper - lower) / 2;
//			if (this.vector [middle].probabilityPartialSum < rnd) {
//				lower = middle + 1;
//			}
//			else {
//				upper = middle - 1;
//			}
//		}
//		return Math.max (0, Math.min (lower, this.length1));
	}
	/**
	 * Distribute the amount of decreased probability of the given slot
	 * among all the other slots.  This method is part of the probability
	 * vector update policy.
	 *
	 * <p> The probability vector contains partial sums. Therefore,
	 * selecting a partner has time complexity {@code log(n)}, however
	 * updating the vector has time complexity {@code O(n)}, where {@code n}
	 * is the number of combinations.  As games are played and if there are
	 * cooperative combinations, there are fewer probability vector updates.
	 *
	 * @param index The slot in the probability vector whose
	 * probability was decreased.
	 */
	public void distributeProbability (int index, int howMuch, int remainderIdx)
	{
		assert howMuch <= this.getRawProbability (index) : "Not enough probability to distribute";
		int distribute = howMuch / this.length1;
		int remainder = howMuch % this.length1;
		int j = 0;
		int i = 0;
		if (remainderIdx < index) {
			for (; i < remainderIdx; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j;
			}
			for (; i < index; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j + remainder;
			}
			this.vector [i].probabilityPartialSum += distribute * j - howMuch + remainder;
			i++;
			for (; i <= this.length1; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j - howMuch + remainder;
			}
		}
		else if (remainderIdx == index) {
			for (; i < index; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j;
			}
			this.vector [i].probabilityPartialSum += distribute * j - howMuch + remainder;
			i++;
			for (; i <= this.length1; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j - howMuch + remainder;
			}
		}
		else {
			for (; i < index; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j;
			}
			this.vector [i].probabilityPartialSum += distribute * j - howMuch;
			i++;
			for (; i < remainderIdx; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j - howMuch;
			}
			for (; i <= this.length1; i++) {
				j++;
				this.vector [i].probabilityPartialSum += distribute * j - howMuch + remainder;
			}
		}
		assert this.vector [this.length1].probabilityPartialSum == this.maxProbability
			: "Last partial sum does not add up to 1.0: "
			+ this.vector [this.length1].probabilityPartialSum;
	}
	/**
	 * Checks if the partial sum of probabilities are correct.  They appear in ascending order in vector {@code vector}.
	 *
	 * <p> The {@code checkXXX()} functions are used as conditions in {@code assert} instructions.
	 */
	private boolean checkProbabilityPartialSums ()
	{
		if (this.vector [0].probabilityPartialSum < 0) {
			return false;
		}
		for (int i = this.length1; i > 0; i--) {
			if (this.vector [i - 1].probabilityPartialSum > this.vector [i].probabilityPartialSum
				|| this.vector [i].probabilityPartialSum < 0) {
				return false;
			}
		}
		return this.vector [this.length1].probabilityPartialSum == this.maxProbability;
	}
	/**
	 * Check field {@code vector}: see if there are no {@code null} elements and the partial sum of probabilities are correct.
	 *
	 * <p> The {@code checkXXX()} functions are used as conditions in {@code assert} instructions.
	 */
	private boolean checkVectorNullElements ()
	{
		for (int i = this.length1; i >= 0; i--) {
			if (this.vector [i] == null) {
				return false;
			}
		}
		return true;
	}
	/**
	 * Perform all checks on field {@code vector}.
	 *
	 * <p> The {@code checkXXX()} functions are used as conditions in {@code assert} instructions.
	 *
	 * @see #checkVectorNullElements()
	 * @see #checkProbabilityPartialSums()
	 */
	private boolean checkVector ()
	{
		return this.checkVectorNullElements () && this.checkProbabilityPartialSums ();
	}
	public String toString ()
	{
		StringBuffer result = new StringBuffer (this.vector.length * 9);
		for (int i = 0; i < this.length1; i++) {
			result.append (this.getRawProbability (i));
			result.append (' ');
		}
		if (this.vector.length > 0) {
			result.append (this.getRawProbability (this.length1));
		}
		return result.toString ();
	}
//	private void writeObject (java.io.ObjectOutputStream out)
//		throws IOException
//	{
//		for (int i = this.vector.length - 1; i >= 0; i--) {
//			out.writeObject (this.vector [i]);
//		}
//	}
//	
//	private void readObject (java.io.ObjectInputStream in)
//		throws IOException, ClassNotFoundException
//	{
//		for (int i = this.vector.length - 1; i >= 0; i--) {
//			this.vector [i] = (S) in.readObject ();
//		}
//	}
//	private void readObjectNoData() 
//		throws ObjectStreamException
//	{
//		
//	}
	/**
	 * Each slot of the probability vector contains a partial sum: the sum of probabilities from that slot to the last slot.
	 */
	static public class Slot
		implements Cloneable
	{
		private int probabilityPartialSum;

		public Slot ()
		{
			
		}
		public Slot (int probabilityPartialSum)
		{
			assert probabilityPartialSum >= 0 : "Partial sum of probabilities must be positive";
			this.probabilityPartialSum = probabilityPartialSum;
		}
		public Slot (Slot other)
		{
			this.probabilityPartialSum = other.probabilityPartialSum;
		}
		public Slot clone ()
		{
			return new Slot (this);
		}
		public int getProbabilityPartialSum ()
		{
			return this.probabilityPartialSum;
		}
	}
}

// Local Variables:
// mode: java
// mode: flyspell-prog
// ispell-local-dictionary: "british"
// End:
